package org.lql.algo.codecrush.hot100.slidingWindow;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: liangqinglong
 * @date: 2025-10-14 10:39
 * @description: 438. 找到字符串中所有字母异位词 <a href="https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class FindAnagrams {

	public List<Integer> findAnagrams(String s, String p) {
		int m = s.length();
		int n = p.length();
		if (m < n) {
			return new ArrayList<>();
		}
		int[] countS = new int[26];
		int[] countP = new int[26];
		for (int i = 0; i < n; i++) {
			countS[s.charAt(i) - 'a']++;
			countP[p.charAt(i) - 'a']++;
		}
		List<Integer> ans = new ArrayList<Integer>();
		if (Arrays.equals(countS, countP)) {
			ans.add(0);
		}
		for (int i = 0; i < m - n; i++) {
			countS[s.charAt(i) - 'a']--;
			countS[s.charAt(i + n) - 'a']++;
			if (Arrays.equals(countS, countP)) {
				ans.add(i+1);
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		FindAnagrams findAnagrams = new FindAnagrams();
		System.out.println(findAnagrams.findAnagrams("cbaebabacd", "abc"));
		System.out.println(findAnagrams.findAnagrams("abab", "ab"));
	}
}
